// 给定一个非负整数数组，你最初位于数组的第一个位置。

// 数组中的每个元素代表你在该位置可以跳跃的最大长度。

// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。

// 示例:

// 输入: [2,3,1,1,4]
// 输出: 2
// 解释: 跳到最后一个位置的最小跳跃数是 2。
//      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<2) return 0;
        int current_max_index=nums[0];
        int pre_max_max_index=nums[0];
        int jump_min=1;
        for(int i=1;i<nums.size();++i){
            if(current_max_index<i){
                ++jump_min;
                current_max_index=pre_max_max_index;
            }
            if(pre_max_max_index<nums[i]+i){
                pre_max_max_index=nums[i]+i;
            }
        }
        return jump_min;
    }
};

class Solution1 {
public:
    int jump(vector<int>& nums) {
        int res{0};
        int n = nums.size();
        int i{0};
        int cur{0}; // 当前能跳到的最远位置
        while (cur < n-1) {
            ++res;
            int pre = cur; // 之前能跳到的最远位置
            for (; i <= pre; ++i) {
                cur = max(cur, i+nums[i]);
            }
            if (pre == cur) return -1;
        }
        return res;
    }
};

class Solution2 {
public:
    int jump(vector<int>& nums) {
        int res = 0, n = nums.size(), last = 0, cur = 0;
        for (int i = 0; i < n - 1; ++i) {
            cur = max(cur, i + nums[i]);
            if (i == last) {
                last = cur;
                ++res;
                if (cur >= n - 1) break;
            }
        }
        return res;
    }
};
